package msb.class05;

import org.junit.Assert;
import org.junit.Test;
import common.util.ArrayUtil;

import java.util.Arrays;

/**
 * 每个数大于右边的数的两倍的个数 ->
 * 2组数据归并的之前，双指针计算
 */
public class Code04_BiggerThanDoubleTwice {
    public int count(int[] arr) {
        return process(arr, 0, arr.length - 1);
    }

    //数据L..R有序
    public static int process(int[] arr, int L, int R) {
        int sum = 0;
        if (L == R) {
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        sum += process(arr, L, mid);
        sum += process(arr, mid + 1, R);
        sum += merge(arr, L, mid, R);
        return sum;
    }

    //L..mid 与 mid+1..R进行归并
    public static int merge(int[] arr, int L, int mid, int R) {

        int count = count(arr, L, mid, R);

        int leftPoint = L;
        int rightPoint = mid + 1;
        int[] tmpArr = new int[R - L + 1];
        int tmpPoint = 0;

        //左右指针越界，归并完整
        while (leftPoint <= mid || rightPoint <= R) {
            //左边指针越界，左边归并完毕，直接取右指针值
            if (leftPoint > mid) {
                tmpArr[tmpPoint++] = arr[rightPoint++];
                continue;
            }
            //右边指针越界，右边归并完毕，直接取左指针值
            if (rightPoint > R) {
                tmpArr[tmpPoint++] = arr[leftPoint++];
                continue;
            }

            //两边都没有越界，取最小值
            if (arr[leftPoint] < arr[rightPoint]) {
                tmpArr[tmpPoint++] = arr[leftPoint++];
            } else {
                tmpArr[tmpPoint++] = arr[rightPoint++];
            }
        }

        for (int i = 0; i < tmpArr.length; i++) {
            arr[L + i] = tmpArr[i];
        }
        return count;
    }

    private static int count(int[] arr, int L, int mid, int R) {
        int leftPoint = L;
        int rightPoint = mid + 1;

        int count = 0;

        while (leftPoint <= mid) {
            //两边都没有越界，取最小值
            while (rightPoint <= R && arr[leftPoint] > arr[rightPoint] * 2) {
                rightPoint++;
            }
            count += rightPoint - (mid + 1);
            leftPoint++;
        }
        return count;
    }

    @Test
    public void check() {
        for (int n = 0; n < 100; n++) {
            int[] instant = ArrayUtil.instantRandom(100, 100);
            System.out.println(Arrays.toString(instant));
            int countExpect = 0;
            int countActual = 0;
            for (int i = 0; i < instant.length; i++) {
                for (int j = i + 1; j < instant.length; j++) {
                    if (instant[i] > instant[j] * 2) {
                        countExpect++;
                    }
                }
            }
            Code04_BiggerThanDoubleTwice code04_biggerThanDoubleTwice = new Code04_BiggerThanDoubleTwice();
            countActual = code04_biggerThanDoubleTwice.count(instant);
            Assert.assertEquals(countExpect, countActual);
        }
    }

    @Test
    public void check2() {
        int[] instant = new int[]{2, 7, 4, 8, 8, 8, 1};
        int countExpect = 0;
        int countActual = 0;
        for (int i = 0; i < instant.length; i++) {
            for (int j = i + 1; j < instant.length; j++) {
                if (instant[i] > instant[j] * 2) {
                    countExpect++;
                }
            }
        }
        Code04_BiggerThanDoubleTwice code04_biggerThanDoubleTwice = new Code04_BiggerThanDoubleTwice();
        countActual = code04_biggerThanDoubleTwice.count(instant);
        Assert.assertEquals(countExpect, countActual);
    }


}
